#include "stack_queue.h"

listNode::listNode() {
    data = 0;
    next = NULL;
}

listNode::listNode(int nodeData, listNode* succ) {
    data = nodeData;
    next = succ;
}

MyStack::MyStack() {
    topNode = NULL;
    stackSize = 0;
}

MyStack::~MyStack() {
    while (topNode != NULL) {
        listNode* temp = topNode;
        topNode = topNode->next;
        delete temp;
    }
}

bool MyStack::push(const int& item) {
    listNode* newNode = new listNode(item, topNode);
    if (newNode == NULL) {
        return false;
    }

    topNode = newNode;
    stackSize++;
    return true;
}

bool MyStack::pop(int& item) {
    if (topNode == NULL) {
        return false;
    }

    listNode* temp = topNode;
    item = topNode->data;
    topNode = topNode->next;
    delete temp;
    stackSize--;
    return true;
}

bool MyStack::getTop(int& item) {
    if (topNode == NULL) {
        return false;
    }

    item = topNode->data;
    return true;
}

void MyStack::printStack() {
    listNode* p = topNode;

    while (p != NULL) {
        if (p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;

    }
}

MyQueue::MyQueue(const int& cap) {
    capacity = cap + 1;
    queue = new int[capacity];
    front = 0;
    rear = 0;
}

MyQueue::~MyQueue() {
    delete[] queue;
}

bool MyQueue::isFull() {
    return (rear + 1) % capacity == front;
}

bool MyQueue::isEmpty() {
    return front == rear;
}

bool MyQueue::enQueue(const int& item) {
    if (isFull()) {
        return false;
    }

    queue[rear] = item;

    rear = (rear + 1) % capacity;

    return true;
}

bool MyQueue::deQueue(int& item) {
    if (isEmpty()) {
        return false;
    }

    item = queue[front];
    front = (front + 1) % capacity;

    return true;
}

bool MyQueue::getFront(int& item) {
    if (isEmpty()) {
        return false;
    }

    item = queue[front];
    return true;
}

void MyQueue::printQueue() {
    int cursor = front;

    while (cursor != rear)
    {
        if ((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

bool postfixExpression(const string& infix, string& result) {
    MyStack opStack;
    result = "";

    MyStack parenStack;
    for (int i = 0; i < infix.length(); i++) {
        char c = infix[i];

        if (c == '(') {
            parenStack.push(1);
        }
        else if (c == ')') {
            int temp;
            if (!parenStack.pop(temp)) {
                result = "Expression is wrong!";
                return false;
            }
        }
    }

    if (!parenStack.isEmpty()) {
        result = "Expression is wrong!";
        return false;
    }

    for (int i = 0; i < infix.length(); i++) {
        char c = infix[i];

        if (isdigit(c)) {
            result += c;
        }
        else if (c == '(') {
            opStack.push(c);
        }
        else if (c == ')') {
            int op;
            while (opStack.getTop(op) && op != '(') {
                opStack.pop(op);
                result += char(op);
            }

            opStack.pop(op);
        }
        else {
            int precedence;

            switch (c) {
            case '+':
            case '-':
                precedence = 1;
                break;
            case '*':
            case '/':
                precedence = 2;
                break;
            default:
                result = "Expression is wrong!";
                return false;
            }

            int topOp;
            while (opStack.getTop(topOp) && topOp != '(') {
                int topPrecedence;
                switch (topOp) {
                case '+':
                case '-':
                    topPrecedence = 1;
                    break;
                case '*':
                case '/':
                    topPrecedence = 2;
                    break;
                default:
                    result = "Expression is wrong!";
                    return false;
                }

                if (topPrecedence >= precedence) {
                    opStack.pop(topOp);
                    result += char(topOp);
                }
                else {
                    break;
                }
            }

            opStack.push(c);
        }
    }

    int op;
    while (opStack.pop(op)) {
        result += char(op);
    }

    return true;
}

bool expressionVal(const string& expression, int& result) {
    string postfix;
    if (!postfixExpression(expression, postfix)) {
        result = 0;
        return false;
    }

    MyStack numStack;

    for (int i = 0; i < postfix.length(); i++) {
        char c = postfix[i];

        if (isdigit(c)) {
            numStack.push(c - '0');
        }
        else {
            int right, left;
            if (!numStack.pop(right) || !numStack.pop(left)) {
                result = 0;
                return false;
            }

            int calcResult = 0;
            switch (c) {
            case '+':
                calcResult = left + right;
                break;
            case '-':
                calcResult = left - right;
                break;
            case '*':
                calcResult = left * right;
                break;
            case '/':
                if (right == 0) {
                    result = 0;
                    return false;
                }
                calcResult = left / right;
                break;
            default:
                result = 0;
                return false;
            }

            numStack.push(calcResult);
        }
    }

    if (!numStack.pop(result)) {
        result = 0;
        return false;
    }

    return true;
}

void yanghui(const int& n) {
    if (n <= 0) {
        return;
    }

    MyQueue prevRow(n + 1);
    MyQueue currentRow(n + 1);

    prevRow.enQueue(1);
    prevRow.enQueue(1);
    prevRow.printQueue();

    for (int i = 2; i <= n; i++) {
        currentRow.enQueue(1);

        int prevVal1, prevVal2;
        prevRow.deQueue(prevVal1);

        for (int j = 1; j < i; j++) {
            prevRow.getFront(prevVal2);
            currentRow.enQueue(prevVal1 + prevVal2);

            prevRow.deQueue(prevVal1);
        }

        currentRow.enQueue(1);

        currentRow.printQueue();

        while (!currentRow.isEmpty()) {
            int temp;
            currentRow.deQueue(temp);
            prevRow.enQueue(temp);
        }
    }
}
